Codeforces Round #205 (Div. 2) B. Two Heaps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Valera has 2·n cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses n cubes and puts them in the first heap. The remaining cubes form the second heap.
Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.
Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?
Input
The first line contains integer n (1 ≤ n ≤ 100). The second line contains 2·n space-separated integers ai (10 ≤ ai ≤ 99), denoting the numbers on the cubes.
Output
In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·n numbers bi (1 ≤ bi ≤ 2). The numbers mean: the i-th cube belongs to the bi-th heap in your division.
If there are multiple optimal ways to split the cubes into the heaps, print any of them.
Sample test(s)
input
1
10 99
output
1
2 1
input
2
13 24 13 45
output
4
1 2 2 1
Note
In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.
In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.
원리는 매우 간단하다. 즉, 가능한 한 두 무더기로 나뉘어야 한다. 예를 들어 1개보다 많은 13이 있다면 두 무더기가 반씩 나누면 가장 큰 것이 아니냐!
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int pri[300],ans[300],x[300],y[300];
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF){
int s[2],x1=0,x2=0;
s[0]=s[1]=0;
memset(pri,0,sizeof(pri));
memset(ans,-1,sizeof(ans));
memset(y,0,sizeof(y));
for(i=0;i<n+n;i++)
scanf("%d",&x[i]),pri[x[i]]++;
int flag=0;
for(i=10;i<100;i++){
if(!pri[i])continue;
if(pri[i]>=2){
s[0]++,s[1]++;
}
else if(pri[i]==1){
ans[i]=s[0]<s[1];
s[0]<s[1]?s[0]++:s[1]++;
}
}
cout<<s[0]*s[1]<<endl;
for(i=10;i<100;i++){
if(!pri[i])continue;
if(pri[i]>=2&&(pri[i]&1)){
ans[i]=s[0]<s[1];
s[0]<s[1]?s[0]++:s[1]++;
}
}
for(int j=0;j<n+n;j++){
i=x[j];
if(j){
if(y[i]<pri[i]/2){printf(" 1");}
else if(y[i]<pri[i]/2+pri[i]/2)printf(" 2");
else printf(" %d",ans[i]+1);
}
else {
if(y[i]<pri[i]/2){printf("1");}
else if(y[i]<pri[i]/2+pri[i]/2)printf("2");
else printf("%d",ans[i]+1);
}
y[i]++;
}
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.